package arrayandlinkedlist

import "sort"

func threeSum(nums []int) [][]int {
	if nums == nil || len(nums) < 3 {
		return nil
	}
	n := len(nums)
	// sort标准库
	sort.Ints(nums)
	// 使用make，才能append
	result := make([][]int, 0)
	for i := 0; i < n-2; {
		j, k, target := i+1, n-1, -nums[i]
		for j < k {
			for j < k && nums[j]+nums[k] > target {
				k--
			}

			if j < k && nums[j]+nums[k] == target {
				// append是builtin标准库
				result = append(result, []int{nums[i], nums[j], nums[k]})
			}

			j++
			for j < k && nums[j] == nums[j-1] {
				j++
			}
		}
		i++
		for i < n-2 && nums[i] == nums[i-1] {
			i++
		}
	}
	return result
}
